// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-05 00:26
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Collections;

public class FindUnsortedSubarrayUpdate {
    /**
     * 最短无序连续子数组->逆向->找连续子数组
     */
    public int findUnsortedSubarray(int[] nums) {
        // 根据比对有序的数据进行定位 -> 主要花费在数组排序
        if (isSort(nums)) {
            // 如果被排序的数组是有序的，则直接返回0
            return 0;
        }
        int n = nums.length;
        int[] copy = new int[n];
        int start = 0, end = n - 1;
        System.arraycopy(nums, 0, copy, 0, n);
        Arrays.sort(copy);
        while (nums[start] == copy[start]) {
            ++start;
        }
        while (nums[end] == copy[end]) {
            --end;
        }
        return end - start + 1;


    }

    /**
     * 判断给定数组是否有序
     *
     * @param nums
     * @return
     */
    private boolean isSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return false;
            }
        }
        return true;
    }


    @Test
    public void shout() {
        // int[] nums = {2, 6, 4, 8, 10, 9, 15};
        //int[] nums = {1, 2, 3, 4};
        // int[] nums = {2, 1};
        int[] nums = {2, 5, 3, 1, 4};
        //int[] nums = {2, 3, 3, 2, 4};
        //int[] nums = {2, 3, 3, 2, 4, 5, 6, 7, 8, 1};
        System.out.println(findUnsortedSubarray(nums));
    }

}
